Computers and workstation terminals, among other devices, have long been organized into networks to allow the various devices, or “nodes,” that are members of the network to transmit and receive data and instructions to and from the other nodes in the network. Information may be passed directly from node to node, or intermediate nodes may relay or route data from the transmitting node to the intended final destination. Industry standard protocols facilitate the communication of nodes within the network. In addition to the nodes themselves, and the protocols that are used for inter-node communication, networks may have a physical infrastructure to allow for the communication among nodes. This infrastructure may either be hard-wired, where communications stay on distinct, physical lines, such as phone lines and fiber optic cables, by wireless communication, where communication is broadcast and received via radio waves, wires and cables being generally replaced with transmitters/receivers and antennas, or a combination of the above.
A node that possesses both a wireless transmitter/receiver that is capable of communicating with the other networked nodes and the communication scheme used by the network may communicate directly with any other node in the wireless network that is within a limited transmit/receive radius from the transmitting node. Communication such as messages that inform nodes within the receive distance of the transmitting node of the existence of the transmitting node in the network, instructions relating to communicating within the network, and bursts of data, called “packets,” may be transmitted and received directly among the various nodes of the network. However, this ability to communicate directly among nodes is inherently limited by both the physical distance and physical obstructions between individual nodes.
Where the distance is too great the signal will degrade and the information received by the destination node will be unreliable or entirely undetectable. Where an obstruction exists between the two nodes, such as walls, buildings or terrain, the signal may be physically blocked from reaching the destination node. Additionally, where the wireless communication is based on the transmission and propagation of electromagnetic waves, the transmitted electromagnetic ways may be subject to interference from other electromagnetic waves that exist in the environment, both from natural and man made sources. Whatever the reason, it may not be possible for every node in a network to communicate directly with every other node in the network.
However, two nodes that are unable to communicate directly, either at all or only in an unreliable manner, may nevertheless be able to communicate indirectly. A third node may be physically positioned in the network such that it may establish reliable communication with both the transmitting and receiving node. The third node may then act as a relay between the two communicating nodes by retransmitting messages it receives from each node that is intended for the other node. The method of using an intermediate node to relay messages between nodes that cannot communicate directly is inherently scaleable, and multiple nodes may be used as relay nodes to facilitate communication by nodes that may be separated by wide physical distances.
In order for a system that utilizes intermediate nodes to facilitate indirect communication among various nodes to function efficiently, it may be necessary for each node to maintain separate lists of all of the nodes in the network, all of the nodes with which that particular node may communicate directly, and which nodes should be used as relay nodes to reach nodes that cannot be reached directly. In other words, each node may need to know the “paths” that route through intermediate relay nodes that the node in question may use to communicate with the other nodes in the network. When the transmitting node knows which path to take to reach a destination node, the transmitting node may direct the communication down that particular path, thereby increasing network efficiency and cutting down on transmit time. And just as each node may maintain the various lists described above, network efficiency may be improved if each node also maintains a list of each path of which that particular node is a part, thereby facilitating the creation of new paths in the event those nodes are added to or deleted from the network.
A network where the positioning and membership of the nodes in the network does not change, a “static” network, may establish and maintain paths among the nodes comparatively easily. Because the physical characteristics of the static network do not frequently change there may be little need to vary paths among nodes. However, many wireless networks are not static. Instead, new nodes may be added and subtracted frequently. Nodes may physically moved or repositioned, altering the direct communication relationships among the nodes. New obstructions may arise to interfere with established paths. A “fluid” situation such as this creates uncertainty as to whether communication among nodes that is possible at any given time will still be possible at a future time, and whether communication among nodes that is not possible will become possible. A static network that tries to function in a fluid environment may quickly become overwhelmed. For this reason, “ad hoc” networks, that allow for nodes to join, move around in, and leave networks seamlessly, have been developed.
One such basic multiple hop, ad hoc wireless communication system is known as the Source-initiated Adaptive Routing Algorithm, or SARA. Every node in a wireless network regularly transmits a message identifying itself as a member of the network. These messages are received by all nodes within range of the node in question, and the receiving nodes also relay the identification message to a node that serves as the network manager. Each node maintains a list of the nodes that are within direct communication range, as well as all of the nodes in the network. When a first node needs to communicate with a second node through a relay path it sends a request message out to the network. As the message propagates through the network, the various paths that the request message takes are recorded, and the first request message to reach the destination node establishes the “best effort” pathway between the two nodes. A confirmation message is sent back to the first node, and subsequent communications between these nodes are conducted down this path, until the path is broken, a predetermined length of time has passed, or any node deliberately breaks off the path.